/**
 * 与G1同，只是MaxV在1E9，分块处理
 * 
 * for 每一个Aj:
 *     如果Aj数量超过3个，计算贡献
 *     if Aj < 1E6:
 *         for Aj的每一个约数i:
 *             ans += Cnt[Aj/i] * Cnt[Aj] * Cnt[Aj * i]
 *             同时 Aj / i 也是约数，要计算贡献
 *     else:
 *         for i in [1...1000]:
 *             if Aj % i == 0:
 *                 ans += Cnt[Aj/i] * Cnt[Aj] * Cnt[Aj * i]
 * 
 * if循环为sqrt(1E6)，而else循环显然为1000
 * 所以整个复杂度为O(1000N)
 * 注意Cnt的键应该使用llt, 因为在if循环中，考虑 Aj / i 时，查询的键会超int
 * wa4应该是由此产生的
 */
#include <bits/stdc++.h>
using namespace std;

using llt = long long;

int N;
vector<int> A;
map<llt, llt> Cnt;
int MaxV;

llt calc(llt x, llt f, llt c){
    auto it = Cnt.find(x / f);
    if(it == Cnt.end()) return 0;
    auto jt = Cnt.find(x * f);
    if(jt == Cnt.end()) return 0;
    return c * it->second * jt->second;
}

llt g(llt v, llt c){
    llt ans = 0;
    for(int i=1;i*i<=v;++i){
        if(v % i) continue;

        if(i != 1) ans += calc(v, i, c);
        if(i * i != v) ans += calc(v, v / i, c);     
    }
    return ans;
}

llt f(llt v, llt c){
    llt ans = 0;
    for(int b=2;;++b){
        if(b * v > MaxV) break;
        if(v % b) continue;
        ans += calc(v, b, c);      
    }    
    return ans;
}

llt proc(){    
    MaxV = (--Cnt.end())->first;    
    llt ans = 0;
    for(const auto & p : Cnt){
        llt c = p.second;
        llt i = p.first;
        if(c >= 3) {
            ans += c * (c - 1) * (c - 2); 
        }
        if(i > 1E6){
            ans += f(i, c);
        }else{
            ans += g(i, c);
        }
    }

    return ans;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
    int nofakse; cin >> nofakse;
    while(nofakse--){
        Cnt.clear();
        cin >> N;
        A.assign(N, 0);
        for(auto & i : A){
            cin >> i;
            ++Cnt[i];
        }
        cout << proc() << endl;
    }
    return 0;
}